package com.company.tanxin;

import java.util.*;

public class MinSetSize {
    public int minSetSize(int[] arr) {
        //获取每一个元素出现的次数
        Map<Integer, Integer> countsMap = new HashMap<>();
        countElements(countsMap, arr);
        //尝试元素的各种组合  计算出现次数 超过一半组合形式
        List<List<Integer>> combinations = new ArrayList<>();
        List<Integer> currentElements = new ArrayList<>();

        //获取组合 元素数量最少的一种
        int minSize = arr.length;
        for (List<Integer> combination : combinations) {
            if (combination.size() < minSize) {
                minSize = combination.size();
            }
        }
        return minSize;
    }


    private void doCombinations(Map<Integer, Integer> countsMap,int[] sourceArr){
        //
        List<List<Integer>> allCombinations = new ArrayList<>();
        List<Integer> currentCombination=new ArrayList<>();

        int l = sourceArr.length/2;

        while (true){
            //计算当前 削减的元素数量
            int cuttentElementsSize =0;
            for (Integer e : currentCombination) {
                cuttentElementsSize+=countsMap.get(e);
            }
            if(cuttentElementsSize<l){//还没有满足条件

            }
        }
    }


    private void countElements(Map<Integer, Integer> coutsMap, int[] source) {
        for (int i : source) {
            if (coutsMap.get(i) != null) {
                coutsMap.put(i, coutsMap.get(i) + 1);
            } else {
                coutsMap.put(i, 1);
            }
        }
    }
}
